package j20251020;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    boolean[] checkCol;
    boolean[] dig1;
    boolean[] dig2;
    char[][] path;
    List<List<String>> ret;
    public List<List<String>> solveNQueens(int n) {
        checkCol=new boolean[n];
        dig1=new boolean[2*n];
        dig2=new boolean[2*n];
        path=new char[n][n];
        ret=new ArrayList<>();
        for(int i=0;i<n;i++)
            Arrays.fill(path[i],'.');
        dfs(n,0);
        return ret;
    }
    public void dfs(int n,int row){
        if(row==n){
            List<String> tmp=new ArrayList<>();
            for(int i=0;i<n;i++){
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }
        for(int col=0;col<n;col++){
            if(checkCol[col]==false&&dig1[row+col]==false&&dig2[row-col+n]==false){
                path[row][col]='Q';
                checkCol[col]=dig1[row+col]=dig2[row-col+n]=true;
                dfs(n,row+1);
                path[row][col]='.';
                checkCol[col]=dig1[row+col]=dig2[row-col+n]=false;
            }
        }
    }
}
